11480. Максимизация прибыли

Ваши алгоритмы стали настолько хороши в прогнозировании рынка, что теперь Вы знаете, какой будет цена акций Wooden Orange Toothpicks Inc. (WOT) в течение следующего количества дней.

Каждый день Вы можете купить одну акцию WOT, продать любое количество принадлежащих вам акций WOT или вообще не совершать никаких сделок. Какую максимальную прибыль можно получить при оптимальной торговой стратегии?

Вход. Первая строка содержит количество предсказанных цен n (1 ≤ n ≤ 50000) для WOT. Следующая строка содержит n целых чисел p_i (1 ≤ p_i ≤ 10⁵), каждое из которых является прогнозируемой ценой акции в i-ый день.

Выход. Выведите максимальную прибыль, которую можно получить на рынке.

Пример входа 1	Пример выхода 1
4 1 4 2 3	4
Пример входа 2	Пример выхода 2
9 5 2 6 9 1 6 5 8 3	26

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть p₀, p₁, …, p_n-1 – цены акций по дням. Вычислим dp_i = max(p_i, …, p_n-1) – максимум на суффиксах массива p. Если в i-ый день купить акцию по цене p_i, то в дальнейшем выгодно продать ее можно будет по наибольшей цене dp_i, получив прибыль dp_i – p_i. Остается вычислить общую прибыль, равную

Пример

Рассмотрим второй тест. Вычислим максимум на суффиксах массива цен акций.

Например, в первый день покупаем акцию за p₁ = 2, и продаем ее в дальнейшем за dp₁ = 9 (продажа совершится на третий день).

Общая прибыль составит 4 + 7 + 3 + 0 + 7 + 2 + 3 + 0 + 0 = 26.

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);

p.resize(n);

dp.resize(n);

for (i = 0; i < n; i++)

scanf("%d", &p[i]);

Вычисляем dp_i = max(p_i, …, p_n-1).

dp[n - 1] = p[n - 1];

for (i = n - 2; i >= 0; i--)

dp[i] = max(p[i], dp[i + 1]);

Вычисляем общую прибыль res. В i-ый день покупаем акцию по цене p_i и в дальнейшем продаем ее за dp_i, получив прибыль dp_i – p_i.

res = 0;

for (i = 0; i < n; i++)

res = res + dp[i] - p[i];

Выводим ответ.

printf("%lld\n", res);

Python реализация

Читаем входные данные.

n = int(input())

p = list(map(int, input().split()))

Вычисляем dp_i = max(p_i, …, p_n-1).

dp = [0] * n

dp[n - 1] = p[n - 1]

for i in range(n - 2, -1, -1):

dp[i] = max(p[i], dp[i + 1])

Вычисляем общую прибыль res. В i-ый день покупаем акцию по цене p_i и в дальнейшем продаем ее за dp_i, получив прибыль dp_i – p_i.

res = 0

for i in range(n):

res += dp[i] - p[i]

Выводим ответ.

print(res)